package com.wangjie.datastructuredesign;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 * @author jieshao
 * @date 2022/5/26 10:57
 *
 * 710. 黑名单中的随机数
 */
public class RandomBlacklist {
    private Map<Integer, Integer> map;
    private Random random;
    private int size;

    public RandomBlacklist(int n, int[] blacklist) {
        map = new HashMap<>();
        random = new Random();
        // 最终数组中的元素个数
        size = n - blacklist.length;
        for (int b : blacklist) {
            map.put(b, 666);
        }
        // 最后一个元素的索引
        int last = n - 1;
        for (int b : blacklist) {
            // 如果 b 已经在区间 [size, n)，可以直接忽略
            if (b >= size) {
                continue;
            }
            while (map.containsKey(last)) {
                last--;
            }
            map.put(b, last);
            last--;
        }
    }

    public int pick() {
        // 随机选取一个索引
        int index = random.nextInt(size);
        // 这个索引命中了黑名单，需要被映射到其它位置
        if (map.containsKey(index)) {
            return map.get(index);
        }
        // 若没有命中黑名单，则直接返回
        return index;
    }
}